#leetcode题目38：外观数列
#难度：中等
#时间复杂度：O(n)
#空间复杂度：O(1)
#方法：模拟

from typing import List
class Solution:
    def countAndSay(self, n: int) -> str:
        def count(s):
            cnt=0
            ans=[]
            for i,c in enumerate(s+"#"):
                if not i or s[i-1]==c:
                    cnt+=1
                if i and c!=s[i-1]:
                    ans.append(str(cnt))
                    ans.append(s[i-1])
                    cnt=1
            return "".join(ans)
        if n==1:
            return "1"
        else:
            return count(self.countAndSay(n-1))

#测试数据
n=1
#预期输出："1"
solution=Solution()
print(solution.countAndSay(n))

n=2
#预期输出："11"
solution=Solution()
print(solution.countAndSay(n))

n=5
#预期输出："111221"
solution=Solution()
print(solution.countAndSay(n))

n=3322251
#预期输出："23321511"
solution=Solution()
print(solution.countAndSay(n))

